In the field of digital communications, forward error correction (FEC) through the application of an error correcting code (ECC) is the technique of encoding messages to add redundancy in order to mitigate the uncertainty introduced by a noisy communication channel, allowing transmission errors to be reduced by a decoder. Generally, an ECC is a technique for converting a sequence of data symbols (representing a message) into a more redundant sequence of code symbols that are transmitted over a noisy channel. A decoder is a system or a method for recovering an estimate of the data symbols from the noisy output of the channel.
A particular family of ECCs called polar codes was introduced by Arikan in 2009, which provides an explicit code construction technique for binary input channels along with a decoder that provably converges toward optimal coding efficiency (i.e., achieving the channel capacity) in the asymptotic of coding over larger blocks of data. The polar codes, as proposed by Arikan, encode a message, represented as a sequence of k data binary symbols (“bits”), into a sequence of n code bits, where n is a power of two in general and larger than k. Specifically, the encoding procedure first writes the k data bits into the vector u:=(u0, . . . , un−1) at the k locations specified by a data index set I ⊂ {0, . . . , n−1} with cardinality |I|=k, while the remaining n−k locations are set to arbitrary, but known, fixed values.
Then, the n coded bits, denoted by the vector c:=(c0, . . . , cn−1), are determined by the formula c=uBF⊗m, where the matrix multiplications are carried out over the binary field (i.e., modulo-2 arithmetic), B denotes the n×n bit-reversal permutation matrix, and F⊗m is the m-th Kronecker power of the matrix
      F    :=          [                                    1                                0                                                1                                1                              ]        ,and m:=log2 n is the polarization stage. A polar code is fully specified by the data index set I and the parameters n and k. Thus, the key to constructing a polar code is choosing a data index set I (equivalently, its complementary set, frozen bit location) suitable for the noisy channel.
The successive cancellation (SC) decoder provided by Arikan helps explaining the specifics of the polar code construction technique. The SC decoder takes as input the noisy output of the channel denoted by y:=(y0, . . . , yn−1), where each yi is a noisy observation of the corresponding code bit ci. The SC decoder proceeds sequentially over the bits, from index 0 to n−1, where for each index i ∈ {0, . . . , (n−1)}, an estimate ûi for bit ui is made as follows: if i ∉ I (i.e., frozen bit location), then ûi is set to the known, fixed value of ui, otherwise, when i ∈ I, ûi is set to the most likely value for ui given the channel outputs y and assuming that the previous estimates (û0, . . . , ûi−1) are correct. Sampling these estimates at the indices i ∈ I gives the estimate for the data bits. Each estimate ûi is made with respect to the conditional distribution P(y, u0, . . . , ui−1|ui), which follows from the polar code structure and underlying channel statistics, and can also be thought to represent a pseudo-channel for the bit ui. With the aim of maximizing the accuracy of the estimates ûi, the data index set I should be chosen to select the k most reliable pseudo-channels.
Polar codes can also be systematically encoded, which is a key property to enable their application in certain concatenated codes. The systematic encoding procedure for polar codes produces a valid codeword such that the data bits appear directly in the codeword at the locations specified by the index J, which denotes the bit-reversal permutation of the locations in I. The system encoding procedure writes the k data bits into a vector u at the locations in J, while the other locations are set to zero, and then applies the polar encoding procedure twice, while setting the frozen bit locations (i.e., the locations not in I) to zero on the intermediate result between the encodings. This procedure is equivalent to applying the formula c=ϕI(uBF⊗m)BF⊗m, where ϕI(·) denotes setting the bits at the locations not in I equal to zero. The codeword c that results from this procedure contains the data bits written at the locations in J, while the remaining locations not in J contain bits called the parity bits. In some situations, it may be convenient to rearrange the codeword c by a permutation that places the k data bit locations (specified by the index set J) first, followed by the n−k parity locations (specified by the complement of the index set J). With such a permutation, the encoding procedure results in the vector of k data bits appended with the n−k parity bits computed by the systematic polar encoding procedure.
Although polar codes asymptotically achieve capacity limit for infinite codeword lengths, the performance at finite codeword lengths can often be inferior to other state-of-the-art ECC codes. The code design for polar codes is conducted by selecting information index I having reliable pseudo-channels. Thus, there are limited degrees of freedom to optimize polar codes, specifically, the combination selecting k locations out of n. In addition, the computational complexity of both encoding and decoding is log-linear, i.e., n log(n), which is more expensive than linear-complexity low-density parity-check codes.
Accordingly, there is a need for a system and method for improving encoding of polar codes with a reduction of computational complexity.